#include <iostream>
#include <vector>
using namespace std;
int nums[200005];
int len;
int pos[200005];
const int INF = 0x3f3f3f3f;

int findFirstBigger(int num, const int nums[], int len){
    int left = 0, right = len-1;
    while(left <= right){
        int mid = left + (right-left) / 2;
        if(nums[mid] < num) left = mid + 1;
        else if(nums[mid] == num) return mid;
        else right = mid-1;
    }
    if(left == len){
        return -1;
    }
    return left;
}

vector<int> LIS(vector<int>& arr){
    for(int i=0;i<arr.size();i++) pos[i] = INF;
    for(int i=0;i<arr.size();i++){
        int p = findFirstBigger(arr[i], nums, len);
        if( p == -1){
            nums[len] = arr[i];
            pos[i] = len;
            len++;
        }else{
            pos[i] = p;
            nums[p] = arr[i];
        }
    }
    vector<int> ans(len);
    int index = len-1;
    for(int i=arr.size()-1;i>=0;i--){
        if(pos[i] == index){
            ans[index] = arr[i];
            index--;
        }
    }
    return ans;
}


int main(){
    vector<int> arr = {2,1,5,3,6,4,8,9,7};
    vector<int> ans = LIS(arr);
    for(int i=0;i<ans.size();i++){
        cout << ans[i] << ", ";
    }

}